package com.fh.binarysearch;

/**
 * 69. x 的平方根
 * @author fuhao
 * @date 2025/10/14 21:48
 */
public class T69MySqrt {

    public class Solution {
        public int mySqrt(int x) {
            if (x < 2) return x; // 处理0和1的情况
            long left = 2;
            long right = x / 2; // 平方根不会超过x/2 (x>=2时)
            while (left <= right) {
                long mid = left + (right - left) / 2;
                long square = mid * mid;
                if (square == x) {
                    return (int) mid;
                } else if (square < x) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return (int) right;
        }
    }
}
